package cn.com.guage.dtm.huawei;

public class guage_二分查找 {

    public static void main(String[] args) {
        //search1();
        search2();
    }


    // 基础二分查找：查找目标值的索引（存在返回索引，否则-1）
    public static int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) { // 注意等号，处理单个元素的情况
            int mid = low + (high - low) / 2; // 避免 (low + high) 溢出
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                low = mid + 1; // 目标在右半区
            } else {
                high = mid - 1; // 目标在左半区
            }
        }
        return -1; // 未找到
    }

    private static void search1() {
        int[] sortedArray = {1, 3, 4, 5, 7, 9, 11, 13, 34, 56, 57, 78, 78, 89, 100};
        int targetExists = 7;
        int targetNotExists = 78;
        System.out.println("目标值 " + targetExists + " 的索引：" + binarySearch(sortedArray, targetExists)); // 输出: 3
        System.out.println("目标值 " + targetNotExists + " 的索引：" + binarySearch(sortedArray, targetNotExists)); // 输出: -1
    }

    private static void search2() {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int targetExists = 10;
        int targetNotExists = 11;
        System.out.println("目标值 " + targetExists + " 的索引：" + binarySearch2(sortedArray, targetExists)); // 输出: 3

    }

    public static int binarySearch2(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sortedArray[mid] == target) {
                return mid;
            } else if (target > sortedArray[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到
    }
}